package com.lark.algorithm.train.onChapter.linkedList;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 示例 2：
 *
 * 输入：head = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1]
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 100] 内
 * 0 <= Node.val <= 100
 * @since 2024-05-22 17:27
 */
public class D20240522Q24_两两交换链表中的节点 {

    // 双指针
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode();
        ListNode endNode = dummyHead;
        ListNode leftNode = head;
        ListNode rightNode = head.next;
        while (rightNode != null) {
            ListNode nextLeftNode = rightNode.next;
            ListNode nextRightNode = nextLeftNode != null ? nextLeftNode.next : null;

            endNode.next = rightNode;
            endNode = endNode.next;
            endNode.next = leftNode;
            endNode = endNode.next;
            leftNode = nextLeftNode;
            rightNode = nextRightNode;
        }
        endNode.next = leftNode;
        return dummyHead.next;
    }

    /**
     * 递归参考：https://lyl0724.github.io/2020/01/25/1/
     * @param head
     * @return
     */
    // 两两交换以head为头节点的链表
    // 返回新链表的头节点
    public ListNode swapPairs2(ListNode head) {
        // 中止条件：当链表只剩一个节点或者没有节点的时候，自然递归就终止了
        if (head == null || head.next == null) {
            return head;
        }
        // 返回值：我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。
        // 本级递归应该做什么：由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点
        ListNode nextNode = head.next;
        head.next = swapPairs2(nextNode.next);
        nextNode.next = head;
        return nextNode;
    }

    public static class ListNode {
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode next;
    }
    
}
